package com.xsherl.leetcode.solution;

import java.util.*;

public class GrayCode {

    /**
     * 格雷编码公式为 f(i) = i XOR i/2;
     */
    public List<Integer> grayCode(int n) {
        if (n == 0){
            return Collections.singletonList(0);
        }
        int len = 1 << n;
        List<Integer> res = new ArrayList<>(len);
        for (int i = 0; i < len; ++i){
            res.add(i ^ (i >> 1));
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 5;
        List<Integer> integers = new GrayCode().grayCode(n);
        System.out.println("[");
        for (int num: integers){
            System.out.println(String.format("%0" + n +"d", Integer.valueOf(Integer.toBinaryString(num))));
        }
        System.out.println("]");
    }
}
